package com.notes.algo.t8.dis;

import java.util.Scanner;

/**
 * @author
 * @Describe 功能描述
 * @date
 */
public class Graph {
    private static int INT_MAX = 1000;
    private int vexNum;
    private int edge;
    private int[][] arc;
    private Dis[] dis;

    public Graph(int vexNum, int edge) {
        this.vexNum = vexNum;
        this.edge = edge;
        arc = new int[vexNum][vexNum];
        dis = new Dis[vexNum];
        for (int i = 0; i < vexNum; i++) {
            arc[i] = new int[vexNum];
            for (int j = 0; j < vexNum; j++) {
                arc[i][j] = INT_MAX;
            }
        }
    }

    public Graph() {

    }

    /**
     * 检查输入的边的信息是否合法
     *
     * @param start
     * @param end
     * @param weight
     * @return
     */
    public boolean checkEdgeValue(int start, int end, int weight) {
        if (start < 1 || end < 1 || start > vexNum || end > vexNum || weight < 0) {
            return false;
        }

        return true;
    }

    /**
     * 创建图
     */
    public void createGraph() {
        Scanner sc = new Scanner(System.in);
        String input;
        int start;
        int end;
        int weight;

        int count = 0;
        while (count != this.edge) {
            input = sc.nextLine();
            String[] arr = input.split(" ", -1);
            start = Integer.valueOf(arr[0]);
            end = Integer.valueOf(arr[1]);
            weight = Integer.valueOf(arr[2]);
            while (!this.checkEdgeValue(start, end, weight)) {
                input = sc.nextLine();
                arr = input.split(" ", -1);
                start = Integer.valueOf(arr[0]);
                end = Integer.valueOf(arr[1]);
                weight = Integer.valueOf(arr[2]);
            }

            // 对邻接矩阵对应上的节点赋值
            arc[start - 1][end - 1] = weight;
            ++count;
        }
    }

    /**
     * 打印邻接矩阵
     */
    public void print() {
        String x = "";
        for (int i = 0; i < vexNum; i ++) {
            x += "v" + i + " \t";
        }
        System.out.println("   " + x);
        for (int i = 0; i < arc.length; i++) {
            int[] curArc = arc[i];
            System.out.print("v" + i + " ");
            for (int j = 0; j < curArc.length; j++) {
                if (curArc[j] == INT_MAX) {
                    System.out.print(INT_MAX + " ");
                } else {
                    System.out.print(curArc[j] + " ");
                }
            }
            System.out.println("");
        }
    }

    public void dis(int begin) {
        // 首先初始化我们的dis数组
        Dis curDis;
        for (int i = 0; i < vexNum; i++) {
            curDis = new Dis();
            // 设置当前的路径
            curDis.setPath("v" + begin + "-->v" + (i + 1));
            curDis.setValue(arc[begin - 1][i]);
            dis[i] = curDis;
        }
        // 设置起点的到起点的路径为0
        Dis beginDis = dis[begin - 1];
        beginDis.setValue(0);
        beginDis.setVisit(true);

        int count = 1;
        // 计算剩余的顶点的最短路径（剩余this->vexnum-1个顶点）
        while (count != vexNum) {
            // temp用于保存当前dis数组中最小值的那个下标
            // min记录的当前的最小值
            int temp = 0;
            int min = INT_MAX;
            for (int i = 0; i < vexNum; i++) {
                Dis dis = this.dis[i];
                if (!dis.isVisit() && dis.getValue() < min) {
                    min = dis.getValue();
                    temp = i;
                }
            }
            // 把temp对应的顶点加入到已经找到的最短路径的集合中
            Dis tmpDis = dis[temp];
            tmpDis.setVisit(true);
            ++count;
            for (int i = 0; i < vexNum; i++) {
                // 注意这里的条件arc[temp][i]!=INT_MAX必须加，不然会出现溢出，从而造成程序异常
                Dis dis = this.dis[i];
                if (!dis.isVisit() && arc[temp][i] != INT_MAX && (tmpDis.getValue() + arc[temp][i]) < dis.getValue()) {
                    // 如果新得到的边可以影响其他未访问的顶点，那就更新它的最短路径和长度
                    dis.setValue(tmpDis.getValue() + arc[temp][i]);
                    dis.setPath(tmpDis.getPath() + "-->v" + (i + 1));
                }
            }
        }
    }

    public void printPath(int begin) {
        String str = "v" + begin;
        System.out.println("以" + str + "为起点的图的最短路径为：");
        for (int i = 0; i != vexNum; i++) {
            Dis dis = this.dis[i];
            if (dis.getValue() != INT_MAX)
                System.out.println(dis.getPath() + "=" + dis.getValue());
            else {
                System.out.println(dis.getPath() + "是无最短路径的");
            }
        }
    }

    public void printPath(int begin, int end) {
        String str = "v" + begin;
        System.out.println("以" + str + "为起点，" + end + "为结束的图的最短路径为：");
        for (int i = 0; i != vexNum; i++) {
            Dis dis = this.dis[i];
            String path = dis.getPath();
            if (path.startsWith("v" + begin) && path.endsWith("v" + end)) {
                if (dis.getValue() != INT_MAX)
                    System.out.println(dis.getPath() + "=" + dis.getValue());
                else {
                    System.out.println(dis.getPath() + "是无最短路径的");
                }
            }
        }
    }

}
